MOD = 10 ** 9 + 7


class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        # 计算每一行的可能性数量
        num = pow(2, m - 1) * 3

        # 构造每一行所有可能的情况
        chance = set()

        def dfs(ii, now):
            if ii == m:
                chance.add(tuple(now))
            else:
                for cc in range(3):
                    if cc != now[-1]:
                        dfs(ii + 1, now + [cc])

        dfs(1, [0])
        dfs(1, [1])
        dfs(1, [2])

        chance = list(chance)

        # print(num, len(stat))

        # 可转移情况
        move = [[False] * num for _ in range(num)]
        for j1 in range(num):
            for j2 in range(num):
                for k in range(m):
                    if chance[j1][k] == chance[j2][k]:
                        break
                else:
                    move[j1][j2] = True

        # 状态转移
        dp1 = [1] * num
        for _ in range(n - 1):
            dp2 = [0] * num
            for j in range(num):
                for i in range(num):
                    if move[i][j]:
                        dp2[j] += dp1[i]
                dp2[j] %= MOD
            dp1 = dp2

        return sum(dp1) % MOD


if __name__ == "__main__":
    print(Solution().colorTheGrid(1, 1))  # 3
    print(Solution().colorTheGrid(1, 2))  # 6
    print(Solution().colorTheGrid(5, 5))  # 580986
